(⑉˙ᗜ˙⑉)
嗨，我是wec，今天是DAY 12。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

House Robber系列的第三道題目!不同於前兩題的線性和環形房屋排列，這次是給定一棵二元樹，每個節點代表一棟房子，節點的值是這棟房子可以偷到的金額。但我們還是不能偷相鄰的房子，而這裡的相鄰是指父節點和子節點，找到再不偷相鄰房屋的前提下可以偷到的最大金額。

🔎 解題思路＆程式碼

1️⃣ 動態規劃

第1步： 對於每次的決定，我們有兩種選擇：
1.偷這棟房子➡️不能偷它的子節點。
2.不偷這棟房子➡️可以偷它的子節點。
第2步： 使用helper函數接收一個節點，返回兩個數組值(偷這個節點的最大金額和不偷這個節點的最大金額)，在用遞迴處理左右子樹，計算最大金額。
第3步： 如果偷當前節點，則它的子節點不能偷，因此總金額是當前節點的值加上左右子節點「不偷」的金額，所以如果不偷當前節點，則可以選擇偷或不偷子節點，取左右子節點的最大值。
第4步： 最後我們取根節點偷或不偷的最大值作為返回的結果。
程式碼：

def rob(root)
  def helper(node)
    return [0, 0] if node.nil?  

    left = helper(node.left)
    right = helper(node.right)
    rob_current = node.val + left[1] + right[1]
    not_rob_current = [left[0], left[1]].max + [right[0], right[1]].max
    [rob_current, not_rob_current]
  end
  result = helper(root)
  [result[0], result[1]].max
end

🔎 總結

時間複雜度

動態規劃： 時間複雜度為O(n)，n為節點數量。
➡️ 終於迎來這系列的後一題!這題真的對比起前兩題有難度多了，在動態規劃的概念中引入二元樹，解題方向也需要點時間思考，因為還要考慮到底要不要偷、偷哪邊，先承認這題在解的時候有偷看solutions(不過因為ruby使用人數不多所以solutions也沒有參考太多)。往後遇到這種二元樹的結構，遞迴絕對是個判斷與計算的好方法
ヽ(^‥^=ゞ)~

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃水果軟糖。
明天要說：Ruby精選刷題！Medium路跑D-5(>∀･)⌒☆